#include<bits/stdc++.h>
using namespace std;
#define maxsize 100

void getnext(int next[],string t)
{
    int j = 0;
    int k = -1;
    next[0] = -1;
    while(j<t.length()-1)
    {
        if(k==-1||t[j]==t[k])
        {
            j++;
            k++;
            next[j] = k;
        }
        else
            k = next[k];
    }
}

void KMP(string s,string t)
{
    int next[maxsize];
    int i = 0;
    int j = 0;
    int m = s.length();
    int n = t.length();
    getnext(next,t);
    while(i<m)
    {
        if(j == n-1&&s[i]==t[j])
        {
            printf("found at %d",i-j);
            j =  next[j];
        }
        if(s[i]==t[j])
        {
            i++;
            j++;
        }
        else
            j = next[j];
            if(j==-1)
            {
                i++;
                j++;
            }
    }
}

int main()
{
    KMP("abababcca","bab");
}